package Leetcode;

import base.ListNode;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */
public class 力扣23_合并K个升序链表 {

    public static void main(String[] args) {
        ListNode a = new ListNode(3);
        ListNode b = new ListNode(6);
        ListNode c = new ListNode(11);
        ListNode d = new ListNode(23);
        ListNode e = new ListNode(30);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;

        ListNode a2 = new ListNode(1);
        ListNode b2 = new ListNode(5);
        ListNode c2 = new ListNode(18);
        ListNode d2 = new ListNode(20);
        ListNode e2 = new ListNode(28);
        a2.next = b2;
        b2.next = c2;
        c2.next = d2;
        d2.next = e2;

        ListNode a3 = new ListNode(2);
        ListNode b3 = new ListNode(9);
        ListNode c3 = new ListNode(12);
        a3.next = b3;
        b3.next = c3;

        ListNode listNode = mergeKLists(new ListNode[]{a, a2, a3});
        System.out.println(listNode);
    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        if (lists.length < 2) {
            return lists[0];
        }
        // 辅助链表
        ListNode a = null;
        for (ListNode list : lists) {
            a = mergeTwoList(a, list);
        }
        return a;
    }

    static ListNode mergeTwoList(ListNode a, ListNode b) {
        // 辅助节点
        ListNode head, pre;
        head = pre = new ListNode();

        while (a != null && b != null) {
            if (a.val <= b.val) {
                ListNode next = a.next;
                pre = pre.next = a;
                a = next;
            } else {
                ListNode next = b.next;
                pre = pre.next = b;
                b = next;
            }
        }

        if (a != null) {
            pre.next = a;
        }
        if (b != null) {
            pre.next = b;
        }

        return head.next;
    }

}
